package com.leetcode.题库;

/**
 * @author 覃国强
 * @date 2022-04-13 20:49
 */
public class 题库_0117_填充每个节点的下一个右侧节点指针II {


  static
  class Solution {
    public Node connect(Node root) {
      if (root == null) {
        return root;
      }
      Node leftmost = root;
      Node nextLeftmost = root;
      while (nextLeftmost != null) {
        Node node = leftmost;
        // 找到下一层的开头
        nextLeftmost = null;
        while (node != null && nextLeftmost == null) {
          if (node.left != null) {
            nextLeftmost = node.left;
            // 如果 leftmost 在左节点，要直接退出，让 node 保持继续位于当前节点，防止错过右节点
            break;
          } else if (node.right != null) {
            nextLeftmost = node.right;
          }
          node = node.next;
        }
        // 利用本层链表将下一层串起来
        Node cur = nextLeftmost;
        while (node != null) {
          Node next = null;
          // 利用本层链表下一层的下一个节点
          while (next == null && node != null) {
            if (node.left != null && cur != node.left) {
              next = node.left;
              // 如果 next 在左节点，要直接退出，让 node 保持继续位于当前节点，防止错过右节点
              break;
            } else if (node.right != null && cur != node.right) {
              next = node.right;
            }
            node = node.next;
          }
          cur.next = next;
          cur = next;
        }
        leftmost = nextLeftmost;
      }
      return root;
    }
  }

  static class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}

    public Node(int val) {
      this.val = val;
    }

    public Node(int val, Node left, Node right, Node next) {
      this.val = val;
      this.left = left;
      this.right = right;
      this.next = next;
    }
  }
}
